#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

// ll qmi(ll a, ll b)
// {
//     ll res = 1;
//     while(b)
//     {
//         res = res * a % mod;
//         b >>= 1;
//         a = a * a % mod;
//     }
//     return res;
// }

int qmi(int a, int b)
{
    int res = 1;
    while(b--) res *= a;
    return res;
}

void solve()
{
    int a, b, l;
    cin >> a >> b >> l;
    int ans = 0;
    for(int i = 1; i <= l / i; i++)
    {
        if(l % i == 0)
        {
            int t1 = i, t2 = l / i;
            for(int j = 0; ; j++)
            {
                int f = 0;
                if(qmi(a, j) > t1) break;
                for(int k = 0; ; k++)
                {
                    if(qmi(a, j) * qmi(b, k) > t1) break;
                    if(qmi(a, j) * qmi(b, k) == t1){
                        ans++;
                        f = 1;
                        break;
                    }
                }
                if(f)break;
            }
            //cout << ans << endl;
            if(t1 != t2)
            {
                //cout << 111 << endl;
                for(int j = 0; ; j++)
                {   //cout << qmi(a, j) << endl;
                    int f = 0;
                    if(qmi(a, j) > t2) break;
                    for(int k = 0; ; k++)
                    {
                        if(qmi(a, j) * qmi(b, k) > t2) break;
                         
                        if(qmi(a, j) * qmi(b, k) == t2){
                            ans++;
                            f = 1;
                            break;
                        }
                    }
                    if(f) break;
                }
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}